package everydayGrade.t4;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.*;

/**
 * @Author: Siantar
 * @Date: 2023-12-21-21:32
 * @Description: 1.0
 */
public class T2866 {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        long[] left = f(maxHeights);
        Collections.reverse(maxHeights);
        long[] right = f(maxHeights);
        long res = left[n - 1];
        for (int i = 0; i < n - 1; i++) {
            res = Math.max(res, left[i] + right[n - i - 2]);
        }
        return res;
    }

    public long[] f(List<Integer> list) {
        int n = list.size();
        long[] leftSum = new long[n];
        Deque<long[]> deque = new ArrayDeque<>();
        deque.push(new long[]{-1, 0, 0});
        for (int i = 0; i < n; i++) {
            int v = list.get(i);
            while (v < deque.peek()[1]) {
                deque.pop();
            }
            long[] iv = deque.peek();
            long index = iv[0], sum = iv[2];
            leftSum[i] = sum + (i - index) * v;
            deque.push(new long[]{i, v, leftSum[i]});
        }
        return leftSum;
    }

    @Test
    public void test() {
        System.out.println(maximumSumOfHeights(Arrays.asList(6, 5, 3, 9, 2, 7)));

    }
}
